The present invention relates to computer cache memory access, and more specifically, to a robust list prefetch implementation for cache access.
Modern microprocessors contain various data prefetch engines to speed memory access. These engines work by detecting prefetch behavior and attempting to guess the next address that will be demand fetched by cache. The engines will then pull into cache the guessed next memory address, thereby improving the efficiency of memory accesses in situations where the guess was correct.
One type of prefetch engine (also referred to herein as a “prefetcher”) is called a list prefetcher. To use a list prefetcher, a first execution of a computer program is run and cache misses (i.e., instances in which data from a memory address requested by the computer program was not stored in cache) are recorded to memory. Upon subsequent executions of the same computer program, the list prefetcher monitors the cache miss activity and attempts to prefetch memory addresses based on the previously-recorded list of historical cache misses.
A shortcoming of the list prefetcher is that it assumes that the memory accesses through multiple executions of the computer program will generally follow the same sequence. Put differently, the list prefetcher assumes that the memory accesses will be essentially the same for each execution of the computer program. However, if the cacheline misses are different in subsequent executions, then the list prefetcher may not be able to use the previously-recorded list of cache miss activity to prefetch information into cache. As a result, the microprocessor may abandon the list prefetcher and resort to a more typical prefetch engine that results in slower overall performance.